Sapling in Zcash

anchor root

https://gyazo.com/ec45950283afa2bc35d45b51844941d3

significantly improved performance: a time reduction of 90% for constructing transactions, and a memory reduction of over 97%.

https://gyazo.com/6abefdef2fe7b417eae7b1368c3240f3

Title: Shielded Hierarchical Deterministic Wallets

code:note.rs

pub struct Note<E: JubjubEngine> {

/// The value of the note

pub value: u64,

/// The diversified base of the address, GH(d)

pub g_d: edwards::Point<E, PrimeOrder>, // DiversifyHash(d)

/// The public key of the address, g_d^ivk

pub pk_d: edwards::Point<E, PrimeOrder>,

/// The commitment randomness

pub r: E::Fs

}

encrypted noteとコミットメントがonchainにmerkle treeで記録される。

tx merkle + rcm merkle

nullifierはnote commitment treeのポジションが明らかになってから計算される。

code:get_nullifier.rs

/// Compute Sapling note nullifier.

pub extern "system" fn librustzcash_sapling_compute_nf(

value: uint64_t,

position: uint64_t,

) -> bool {

np(note plaintext)は以下の要素からなる。

divifier, value, rcm, memo

8 bit (0x01) sapling note plaintextのversionを示す識別子

11bytes d

8bytes v

32bytes rcm

512bytes memo

encrypted note

diversified transmission key (pk_d)で暗号化される。

Spend transfers

古いnoteを消費する。Tx内に保持。

noteのpedersen value commitment

spend statement (snark proof)

anchor

Spend Descriptions

cv: input noteのvalue commitment

rt: 前ブロックのtreestateのoutput (commitmentのmerkle tree）

nf: input noteのnullifier

rk: spend descriptionの署名を検証できる公開鍵

zk proof

spendAuthSig: 署名

署名の検証

Txのハッシュ値がSIGHASHと一致しないか。

Spend Statement

primary input

rt

cv

nf

rk

auxiliary input

path

position

g

pk

v

rcv

cm

rcm

alpha

ak

nsk

conditions

Note commitment integrity

Merkle path validity

Value commitment integrity

small order checks

nullifier integrity

spend authority

diversified address integrity

Output transfers

新しいnoteを生成する。Tx内に保持。

new noteのpedersen value commitment

output statement (snark proof)

Output descriptions

cv: output noteのvalue commitment

cm: output noteのcommitment

epk: noteを暗号化した公開鍵

C^{enc}: 暗号化されたoutput note

C^{out}: output noteを復号化できるephemeral private key

zk proof

Output statements

primary

cv

vm

epk

auxiliary

g

pk

v

rcv

rcm

esk

conditions

Note commiment integrity

Value commitment integrity

small order check

Ephemeral public key integrity

Blockchain Scanning

n = (d, pk_d, v, rcm) : note commitment

np = d, v, rcm, memo : note plaintext

それぞれのトランザクションに対して、

Txのoutput descriptionと(note positionを与えて）

Incoming viewing keyを使ってnote ciphertextを復号化し、npを得る。

npからn とmemoを得る。

nkを使ってnとposからnullifierを計算する

nullifiermap: nf => n に追加する。

Txのspend descriptionについて、

spend descriptionのnullifierがすでにnullifierMapに存在した場合、SpentSetにNullifierMap(nf)(i.e.=n)を追加する。

signature

PureEdJubjub-BLAKE2b and RedDSA

Efficient Unlinkable Sanitizable Signatures from Signatures with Re-Randomizable Keys

multi signature

commitment tree

トランザクションごとにNote commitment treeのstateは変化するので、Tx内にそのrootを保持しproof of includeを行う。ブロック最後のtxについては次ブロックにstateを引き継ぐためにheaderに最後のstateのrootを記録する。

Sprout

inputの関係のないTxのハッシュをdataToBeSignedとしそれぞれのTxに対して生成したephemeral JoinSplitSig key pairのprivate keyにより署名され、対応する検証鍵はTxにencodingされ含められる。

Note暗号化の公開鍵と署名の検証鍵は同じ？

zero cash

Individual Zerocash nodes maintain a Merkle tree over all of the coin commitments seen thus far. Any user can then demonstrate ownership of a coin commitment, via its decommitted values as well as a short witness of membership in the tree. Unfortunately, merely publishing this information as an "ownership proof" is not private; instead, to achieve privacy, we rely on a second type of transaction, which allows a user to prove, in zero knowledge, that he knows such information.

Sprout z-address

現状のz-addressは以下のよう。

zcA6qngiR3U7HxYopyTWkaDLwYBd83D5MT7Jb9gpgTzPLMZytzRbtdPP1Syv4RvRgHeoZrJWSask3DyfwXG9DGPMWMvX7aC

zs1z7rejlpsa98s2rrrfkwmaxu53e4ue0ulcrw0h4x5g8jl04tak0d3mm47vdtahatqrlkngh9slyP

Decoupled Spend Authority

JubJub

code:jubjub.rs

/// The pre-computed parameters for Jubjub, including curve

/// constants and various limits and window tables.

pub trait JubjubParams<E: JubjubEngine>: Sized {

fn edwards_d(&self) -> &E::Fr;

fn montgomery_a(&self) -> &E::Fr;

fn montgomery_2a(&self) -> &E::Fr;

/// The scaling factor used for conversion from the Montgomery form.

fn scale(&self) -> &E::Fr;

/// Returns the generators (for each segment) used in all Pedersen commitments.

/// Returns the exp table for Pedersen hashes.

/// Returns the maximum number of chunks per segment of the Pedersen hash.

fn pedersen_hash_chunks_per_generator(&self) -> usize;

/// magnitudes of the Pedersen hash segment generators.

/// Returns the number of chunks needed to represent a full scalar during fixed-base

/// exponentiation.

fn fixed_base_chunks_per_generator(&self) -> usize;

/// Returns a fixed generator.

fn generator(&self, base: FixedGenerators) -> &edwards::Point<E, PrimeOrder>;

/// fixed generator.

/// Returns the window size for exponentiation of Pedersen hash generators

/// outside the circuit

fn pedersen_hash_exp_window_size() -> u32;

}

code:point.rs

// Represents the affine point (X/Z, Y/Z) via the extended

// twisted Edwards coordinates.

//

// See "Twisted Edwards Curves Revisited"

// Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson

pub struct Point<E: JubjubEngine, Subgroup> {

x: E::Fr,

y: E::Fr,

t: E::Fr,

z: E::Fr,

_marker: PhantomData<Subgroup>

}

Sapling: Choose CRH used to derive ivk and nr

re-randomizationをサポートするschnorr-baseのredDSAがjubjub curveで動作するredJubub

bls12-381のsubgroup order(r)がjubjubのbase field modulus(q)に対応するinner curve

jubjubのcofactor=8であり、より小さいsubgroupをもつ

F_sがbls12-381のsubgroup orderとjubjubのbase field modulusに対応し、F_rがjubjubのsubgroup orderに対応する

Bls12 structにjubjubEngine traitも実装されている

G2はtwisted側のジェネラータポイント

Address encording

https://gyazo.com/744067ca1c97b00e1ae73108f6e7baa2

LEBS2OSP

defined as follows: pad the input on the right with 8·ceiling ?/8 −? ? ?

zero bits so that its length is a multiple of 8 bits. Then convert each group of 8 bits to a byte value with the least significant bit first, and concatenate the resulting bytes in the same order as the groups.

jubjubのcofactorが8だから。

diversifierがランダムオラクルとして作用しjubjub curve上の点を取っている。

=> dとg_dのunklinkability

In ZIP-32 an 88-bit Pseudo Random Permutation, keyed differently for each node of the derivation tree, is used to select new diversifiers. This resolves the potential problem, provided that the input to the Pseudo Random Permutation does not repeat for a given node.

https://gyazo.com/876bee913e6e5c62c41c39a5e80016a2

utxo vs account

SIGHASH

The biggest issue with zcash (and monero too) is nullifiers' set growing linearly and having uniform access pattern. After 100B transactions you have 3.2TB of nullifiers that all must be kept in fast RAM by all nodes for verification.

Sapling MPC